Méthode de type off-policy avec approximations

8. Méthodes par Gradient-TD

8.2. Construction de l'algorithme

La forme générale de notre algorithme SGD va mettre à jour le vecteur poids de la manière suivante :

$${\textbf{w}_{t + 1}} = {\textbf{w}_t} - \frac{1}{2}\alpha \nabla \overline {PBE} \left( \textbf{w} \right)$$

On a donc besoin de trouver l'expression du gradient du projeté de l'erreur de Bellman.

Expression du gradient du projeté de l'erreur de Bellman

On commence par exprimer le projeté de l'erreur de Bellman sous forme matricielle:

$\quad \quad \quad \overline {PBE} \left( \textbf{w} \right) = \left\| {\prod \overline {{\delta _\textbf{w}}} } \right\|_\mu ^2 = {\left( {\prod \overline {{\delta _\textbf{w}}} } \right)^T}D\prod \overline {{\delta _\textbf{w}}}$

$\quad \quad \quad \quad \quad \quad \: \: \quad= {\overline {{\delta _\textbf{w}}} ^T}\prod^T D\prod \overline {{\delta _\textbf{w}}}$

Le terme $\prod^T D\prod$ vaut :

$\quad \quad \quad {\prod ^T}D\prod = {\left[ {X{{\left( {{X^T}DX} \right)}^{ - 1}}{X^T}D} \right]^T}DX{\left( {{X^T}DX} \right)^{ - 1}}{X^T}D$

$\quad \quad \quad \quad \quad \: \: \: \quad = {D^T}X{\left[ {{{\left( {{X^T}DX} \right)}^{ - 1}}} \right]^T}{X^T}DX{\left( {{X^T}DX} \right)^{ - 1}}{X^T}D$

$\quad \quad \quad \quad \quad \: \: \: \quad = {D^T}X{\left[ {{{\left( {{X^T}DX} \right)}^{ - 1}}} \right]^T}{X^T}D\underbrace {X{X^{ - 1}}{D^{ - 1}}{{\left( {{X^T}} \right)}^{ - 1}}{X^T}D}_{ = I}$

$ \quad \quad \quad \quad \quad \: \: \: \quad = {D^T}X{\left[ {{X^{ - 1}}{D^{ - 1}}{{\left( {{X^T}} \right)}^{ - 1}}} \right]^T}{X^T}D$

$ \quad \quad \quad \quad \quad \: \: \: \quad = {D^T}X{\left( {{{\left( {{X^T}} \right)}^{ - 1}}} \right)^T}{\left( {{D^{ - 1}}} \right)^T}{\left( {{X^{ - 1}}} \right)^T}{X^T}D$

$\quad \quad \quad \quad \quad \: \: \: \quad = DX{X^{ - 1}}{D^{ - 1}}{\left( {{X^T}} \right)^{ - 1}}{X^T}D$ $\quad \quad$ (car $D^T=D$ et ${\left( {{X^T}} \right)^{ - 1}} = {\left( {{X^{ - 1}}} \right)^T}$)

$\quad \quad \quad {\prod ^T}D\prod = DX{\left( {{X^T}DX} \right)^{ - 1}}{X^T}D$

L'expression du projeté de l'erreur de Bellman devient donc :

$\quad \quad \quad \overline {PBE} \left( \textbf{w} \right) = {\overline {{\delta _\textbf{w}}} ^T}DX{\left( {{X^T}DX} \right)^{ - 1}}{X^T}D\overline {{\delta _\textbf{w}}}$

$\quad \quad \quad \overline {PBE} \left( \textbf{w} \right) = {\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)^T}{\left( {{X^T}DX} \right)^{ - 1}}\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)$

Il faut maintenant calculer le gradient du projeté :

$\nabla \overline {PBE} \left( \textbf{w} \right) = \nabla \left[ {{{\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)}^T}} \right]{\left( {{X^T}DX} \right)^{ - 1}}\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)$

$\quad \quad \quad \quad \quad \quad + {\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)^T}\nabla \left[ {{{\left( {{X^T}DX} \right)}^{ - 1}}} \right]\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)$

$ \quad \quad \quad \quad \quad \quad+ {\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)^T}{\left( {{X^T}DX} \right)^{ - 1}}\nabla \left[ {\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)} \right]$

$ \nabla \overline {PBE} \left( \textbf{w} \right) = \nabla \left[ {{{\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)}^T}} \right]{\left( {{X^T}DX} \right)^{ - 1}}\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)$

$ \quad \quad \quad \quad \quad \quad + {\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)^T}{\left( {{X^T}DX} \right)^{ - 1}}\nabla \left[ {\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)} \right]$

Comme $\frac{{\partial \left( {{v^T}a} \right)}}{{\partial v}} = \frac{{\partial {{\left( {{v^T}a} \right)}^T}}}{{\partial v}}$ on obtient :

$$\nabla \overline {PBE} \left( \textbf{w} \right) = 2\nabla {\left[ {{X^T}D\overline {{\delta _\textbf{w}}} } \right]^T}{\left( {{X^T}DX} \right)^{ - 1}}\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right)$$

Analyse du gradient

Regardons l'expression du produit des deux paquets de droite :

$${\left( {{X^T}DX} \right)^{ - 1}}\left( {{X^T}D\overline {{\delta _\textbf{w}}} } \right) = {\left( {{X^T}DX} \right)^{ - 1}}{X^T}D\overline \delta _\textbf{w}$$

Et comparons-la avec l'expression du projeté orthogonal d'un vecteur $V_\pi$ sur le sous-espace vectoriel des foncions d'approximations :

$${V_\textbf{w}} = X\textbf{w} = X{\left( {{X^T}DX} \right)^{ - 1}}{X^T}D{V_\pi }$$

On identifie donc que l'expression ${\left( {{X^T}DX} \right)^{ - 1}}{X^T}D\overline \delta _\textbf{w}$ correspond à la valeur d'un vecteur poids $\textbf{v}$ optimale qui minimiserait la norme suivante:

$$\left\| {\overline {{\delta _\textbf{w}}} - X\textbf{v}} \right\|_\mu ^2$$

L'expression ${\left( {{X^T}DX} \right)^{ - 1}}{X^T}D\overline \delta _\textbf{w}$ est donc la solution d'un problème de régression pour lequel on chercherait à trouver le meilleur vecteur $\textbf{v}$ permettant d'approximer le vecteur ${\overline {{\delta _\textbf{w}}} }$ sous la forme $X\textbf{v}$, c'est-à-dire à partir des vecteurs caractéristiques $\textbf{x}(s)$. C'est donc l'expression du poids $\textbf{v}$ qui permet de minimiser l'erreur suivante :

$$\left\| {\overline {{\delta _\textbf{w}}} - X\textbf{v}} \right\|_\mu ^2 = \sum\limits_{s \in S} {\mu \left( s \right)} {\left( {E\left[ {{\delta _t} - {\textbf{v}^T}\textbf{x}\left( s \right)|{S_t} = s,{A_t} \sim \pi } \right]} \right)^2}$$

Donc minimiser l'erreur : ${\left( {{\delta _t} - {\textbf{v}^T}{\textbf{x}_t}} \right)^2}$

Pour calculer ce vecteur $\textbf{v}$ on mettra donc en place l'algorithme suivant :

$${\textbf{v}_{t + 1}} = {\textbf{v}_t} - \frac{1}{2}\beta \nabla {\left( {{\delta _t} - {{\bf{v}}^T}{{\bf{x}}_t}} \right)^2}$$

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = {\textbf{v}_t} - \beta \left( {{\delta _t} - {{\bf{v}}^T}{{\bf{x}}_t}} \right)\nabla \left( {{\delta _t} - {{\bf{v}}^T}{{\bf{x}}_t}} \right)$

$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = {\textbf{v}_t} + \beta \left( {{\delta _t} - {{\bf{v}}^T}{{\bf{x}}_t}} \right)\nabla \left( {{{\bf{v}}^T}{{\bf{x}}_t}} \right)$

$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = {\textbf{v}_t} + \beta \left( {{\delta _t} - {{\bf{v}}^T}{{\bf{x}}_t}} \right){{\bf{x}}_t}$

Puisque l'apprentissage se fait hors-ligne sous la stratégie d'exploitation $b$, il faut pondérer la mise à jour du vecteur poids avec le ratio d'échantillonnage préférentiel. Ceci nous amène au résultat final :

$${\textbf{v}_{t + 1}} = {\textbf{v}_t} + \beta {\rho _t}\left( {{\delta _t} - {{\bf{v_t}}^T}{{\bf{x}}_t}} \right){{\bf{x}}_t}$$

avec $\beta>0$ le taux d'apprentissage ciblant le calcul du vecteur poids $\textbf{v}$.

Rappelons l'expression de l'erreur TD(0):

$${\delta _t} = {R_{t + 1}} + \gamma \hat v\left( {{S_{t + 1}},{\textbf{w}_t}} \right) - \hat v\left( {{S_t},{\textbf{w}_t}} \right)$$

On obtient donc, puisque $\hat v\left( {{S_t},{\textbf{w}_t}} \right) = {\textbf{w}^T}{\textbf{x}_t}$:

$${{\bf{v}}_{t + 1}} = {{\bf{v}}_t} + \beta {\rho _t}\left[ {{R_{t + 1}} + {\textbf{w}_t^T}\left( {\gamma {\textbf{x}_{t + 1}} - {\textbf{x}_t}} \right) - {{\bf{v}}_t}^T{{\bf{x}}_t}} \right]{{\bf{x}}_t}$$

Algorithme GTD

Connaissant le vecteur poids $\textbf{v}$, le gradient du projeté de l'erreur de Bellman est s'écrit maintenant:

$$\nabla \overline {PBE} \left( \textbf{w} \right) = 2\nabla {\left[ {{X^T}D\overline {{\delta _\textbf{w}}} } \right]^T}\textbf{v}$$

La mise à jour se fait avec l'algorithme SGD:

$${\textbf{w}_{t + 1}} = {\textbf{w}_t} - \frac{1}{2}\alpha \nabla \overline {PBE} \left( \textbf{w} \right)$$

$ \quad \quad \quad \quad \quad \quad \quad \: \: \: \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = {\textbf{w}_t} - \alpha \nabla {\left[ {{X^T}D\overline {{\delta _\textbf{w}}} } \right]^T}\textbf{v}$

Le facteur $\nabla {\left[ {{X^T}D\overline {{\delta _\textbf{w}}} } \right]^T}$ peut s'écrire sous forme d'espérance mathématique :

$$\nabla {\left[ {{X^T}D\overline {{\delta _\textbf{w}}} } \right]^T} = \nabla {\left[ {\sum\limits_{s \in S} {\mu \left( s \right)\textbf{x}\left( s \right)} \overline {{\delta _\textbf{w}}} \left( s \right)} \right]^T}$$

$\quad \quad \quad \quad \quad \quad \quad \: \: \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = \nabla \left[ {\sum\limits_{s \in S} {\mu \left( s \right)} {{\overline {{\delta _\textbf{w}}} }^T}\left( s \right){\textbf{x}^T}\left( s \right)} \right]$

$\quad \quad \quad \quad \quad \quad \quad \: \: \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = \nabla \left[ {E\left[ {{\delta _t}^T{\textbf{x}_t}^T|{S_t} = s,{A_t} \sim \pi } \right]} \right]$

$ \quad \quad \quad \quad \quad \quad \quad \: \: \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad= \nabla \left[ {E\left[ {{\rho _t}{\delta _t}^T{\textbf{x}_t}^T|{S_t} = s,{A_t} \sim b} \right]} \right]$

$ \quad \quad \quad \quad \quad \quad \quad \: \: \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = E\left[ {{\rho _t}\nabla \left( {{\delta _t}^T{\textbf{x}_t}^T|{S_t} = s,{A_t} \sim b} \right)} \right]$

$\quad \quad \quad \quad \quad \quad \quad \: \: \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad = E\left[ {{\rho _t}\nabla \left( {\left( {{R_{t + 1}} + \gamma {\textbf{w}_t^T}{\textbf{x}_{t + 1}} - {\textbf{w}_t^T}{\textbf{x}_t}} \right)^T{\textbf{x}_t}^T|{S_t} = s,{A_t} \sim b} \right)} \right]$

$ \quad \quad \quad \quad \quad \quad \quad \: \: \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad= E\left[ {{\rho _t}\left( {\gamma {\textbf{x}_{t + 1}} - {\textbf{x}_t}} \right){\textbf{x}_t}^T|{S_t} = s,{A_t} \sim b} \right]$

Finalement, on obtient donc l'algorithme suivant :

$$\left\{ \begin{array}{l} {\textbf{w}_{t + 1}} = {\textbf{w}_t} + \alpha {\rho _t}\left( {{\textbf{x}_t} - \gamma {\textbf{x}_{t + 1}}} \right){\textbf{x}_t}^T{\textbf{v}_t}\\ {{\bf{v}}_{t + 1}} = {{\bf{v}}_t} + \beta {\rho _t}\left[ {{R_{t + 1}} + {{\bf{w}_t}^T}\left( {\gamma {{\bf{x}}_{t + 1}} - {{\bf{x}}_t}} \right) - {{\bf{v}}_t}^T{{\bf{x}}_t}} \right]{{\bf{x}}_t} \end{array} \right.$$